package leetcode;

import javafx.util.Pair;

import java.util.*;


class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}


@SuppressWarnings({"all"})
public class Demo6 {


    //429. N 叉树的层序遍历
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                Node front = queue.poll();
                list.add(front.val);
                for(Node node : front.children) {
                    if(node != null) queue.offer(node);
                }
            }
            ret.add(list);
        }
        return ret;
    }



    //103. 二叉树的锯齿形层序遍历
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int flag = 1;   // 记录奇数、偶数行

        while(!q.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int sz = q.size();
            for(int i = 0; i < sz; i++) {
                TreeNode front = q.poll();
                list.add(front.val);
                if(front.left != null) q.offer(front.left);
                if(front.right != null) q.offer(front.right);
            }
            if(flag++ % 2 == 0) Collections.reverse(list);
            ret.add(list);
        }

        return ret;
    }



    //LCR 044. 在每个树行中找最大值
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()) {
            long max = Long.MIN_VALUE;
            int sz = q.size();
            for(int i = 0; i < sz; i++) {
                TreeNode front = q.poll();
                max = Math.max(max, front.val);
                if(front.left != null) q.offer(front.left);
                if(front.right != null) q.offer(front.right);
            }
            ret.add((int) max);
        }
        return ret;

    }



    //662. 二叉树最大宽度
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode, Integer>> q = new ArrayList<>();
        q.add(new Pair<>(root, 1));
        int ret = 1;

        while(q.size() > 0) {
            // 根据本层信息更新结果
            Pair<TreeNode, Integer> p1 = q.get(0);
            Pair<TreeNode, Integer> p2 = q.get(q.size()-1);
            ret = Math.max(p2.getValue() - p1.getValue() + 1, ret);
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            int sz = q.size();

            // 将下一层结果存储到一个临时数组，循环结束后 把临时数组赋值给 q
            for(int i = 0; i < sz; i++) {
                Pair<TreeNode, Integer> pair = q.get(i);
                if(pair.getKey().left != null) {
                    tmp.add(new Pair<TreeNode, Integer>(pair.getKey().left, pair.getValue() * 2));
                }
                if(pair.getKey().right != null) {
                    tmp.add(new Pair<TreeNode, Integer>(pair.getKey().right, pair.getValue() * 2 + 1));
                }
            }
            q = tmp;
        }

        return ret;
    }



    //14. 最长公共前缀
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 1) return strs[0];
        int len = 201;
        for(String str : strs) {
            len = Math.min(len, str.length());
        }

        StringBuffer ret = new StringBuffer();
        for(int i = 0; i < len; i++) {
            char ch = strs[0].charAt(i);
            for(int j = 1; j < strs.length; j++) {
                if(ch != strs[j].charAt(i)) {
                    return ret.toString();
                }
            }
            ret.append(ch);
        }
        return ret.toString();
    }




    //692. 前K个高频单词
    public List<String> topKFrequent(String[] words, int k) {
        // 1. 统计各个单词出现的次数
        Map<String, Integer> hash = new HashMap<>();
        for(String s : words) {
            hash.put(s, hash.getOrDefault(s, 0) + 1);
        }

        // 2. 建立一个以单词出现次数的小根堆，以字典顺序的大根堆
        PriorityQueue<Pair<String, Integer>> q = new PriorityQueue<>((o1, o2) -> {
            if(!o1.getValue().equals(o2.getValue())) {
                return o1.getValue() - o2.getValue();
            } else {
                return o2.getKey().compareTo(o1.getKey());
            }
        });

        // 3. 将所有单词依次放入优先队列
        for(Map.Entry<String, Integer> entry : hash.entrySet()) {
            q.offer(new Pair<>(entry.getKey(), entry.getValue()));
            if(q.size() > k) {
                q.poll();
            }
        }

        // 4. 将堆中结果放入结果集
        List<String> ret = new ArrayList<>();
        while(!q.isEmpty()) {
            ret.add(q.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }



    //295. 数据流的中位数
    class MedianFinder {
        PriorityQueue<Integer> maxHeap;     // 存储前半部分的较小元素
        PriorityQueue<Integer> minHeap;     // 存储后半部分的较大元素

        public MedianFinder() {
            maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
            minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
        }

        public void addNum(int num) {
            if(maxHeap.size() == minHeap.size()) {
                if(maxHeap.isEmpty() || num < maxHeap.peek()) {
                    maxHeap.add(num);
                } else {
                    minHeap.add(num);
                    maxHeap.add(minHeap.poll());
                }
            } else {
                // 把元素加入小根堆
                if(num < maxHeap.peek()) {
                    minHeap.add(maxHeap.poll());
                    maxHeap.add(num);
                }else {
                    minHeap.add(num);
                }
            }
        }

        public double findMedian() {
            if(maxHeap.size() == minHeap.size()) return (maxHeap.peek() + minHeap.peek()) / 2.0;
            else return (double)maxHeap.peek();
        }
    }



    // 200. 岛屿数量
    // int row, col, ret;
    //    boolean[][] visit;
    //    int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public int numIslands(char[][] grid) {
    //        row = grid.length;
    //        col = grid[0].length;
    //        visit = new boolean[row][col];
    //
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(grid[i][j] == '1' && !visit[i][j]) {
    //                    bfs(grid, new int[]{i, j});
    //                    ret++;
    //                }
    //            }
    //        }
    //        return ret;
    //    }
    //
    //    public void bfs(char[][] grid, int[] pos) {
    //        Queue<int[]> q = new LinkedList<>();
    //        q.offer(pos);
    //        while(!q.isEmpty()) {
    //            int[] arr = q.poll();
    //            int i = arr[0], j = arr[1];
    //            visit[i][j] = true;
    //            for(int k = 0; k < 4; k++) {
    //                int x = i + dx[k], y = j + dy[k];
    //                if(x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == '1' && !visit[x][y]) {
    //                    q.offer(new int[]{x, y});
    //                    visit[x][y] = true;
    //                }
    //            }
    //        }
    //    }



    //695. 岛屿的最大面积
    //int row, col, ret, count;
    //    boolean[][] visit;
    //    int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public int maxAreaOfIsland(int[][] grid) {
    //        row = grid.length;
    //        col = grid[0].length;
    //        visit = new boolean[row][col];
    //
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(grid[i][j] == 1 && !visit[i][j]) {
    //                    count = 0;
    //                    bfs(grid, new int[]{i, j});
    //                    ret = Math.max(ret, count);
    //                }
    //            }
    //        }
    //        return ret;
    //    }
    //
    //    private void bfs(int[][] grid, int[]pos) {
    //        Queue<int[]> q = new LinkedList<>();
    //        q.offer(pos);
    //        visit[pos[0]][pos[1]] = true;
    //        count++;
    //
    //        while(!q.isEmpty()) {
    //            int[] arr = q.poll();
    //            int i = arr[0], j = arr[1];
    //            for(int k = 0; k < 4; k++) {
    //                int x = i + dx[k], y = j + dy[k];
    //                if(x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == 1 && !visit[x][y]) {
    //                    q.offer(new int[]{x, y});
    //                    visit[x][y] = true;
    //                    count++;
    //                }
    //            }
    //        }
    //    }




    //130. 被围绕的区域
    //int row, col;
    //    int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public void solve(char[][] board) {
    //        row = board.length;
    //        col = board[0].length;
    //        //visit = new boolean[row][col];
    //
    //        // 1. 将处于边界的连通 'O'变成 '.'
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(i == 0 || i == row - 1 || j == 0 || j == col - 1) {
    //                    if(board[i][j] == 'O') bfs(board, new int[]{i, j});
    //                }
    //            }
    //        }
    //
    //        // 2. 遍历棋盘，将所有'.'变成 ‘O’,将所有的‘O’变成‘X’
    //         for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(board[i][j] == '.') board[i][j] = 'O';
    //                else if(board[i][j] == 'O') board[i][j] = 'X';
    //            }
    //        }
    //    }
    //
    //    private void bfs(char[][] board, int[] pos) {
    //        Queue<int[]> q = new LinkedList<>();
    //        q.offer(pos);
    //        board[pos[0]][pos[1]] = '.';
    //
    //        while(!q.isEmpty()) {
    //            int[] arr = q.poll();
    //            int i = arr[0], j = arr[1];
    //            for(int k = 0; k < 4; k++) {
    //                int x = i + dx[k], y = j + dy[k];
    //                if(x >= 0 && x < row && y >= 0 && y < col && board[x][y] == 'O') {
    //                    q.offer(new int[]{x, y});
    //                    board[x][y] = '.';
    //                }
    //            }
    //        }
    //
    //    }



    //1926. 迷宫中离入口最近的出口
    //int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public int nearestExit(char[][] maze, int[] entrance) {
    //        int row = maze.length, col = maze[0].length,  ret = -1;
    //        boolean[][] visit = new boolean[row][col];
    //
    //        Queue<int[]> q = new LinkedList<>();
    //        q.offer(entrance);
    //        visit[entrance[0]][entrance[1]] = true;
    //
    //        while(!q.isEmpty()) {
    //            int sz = q.size();
    //            ret++;
    //            // 每一层结点的遍历
    //            for(int a = 0; a < sz; a++) {
    //                int[] t = q.poll();
    //                int i = t[0], j = t[1];
    //                // 当前层数为 0 时，证明入口位置是出口位置
    //                if((i == 0 || i == row - 1 || j == 0 || j == col - 1) && ret != 0) return ret;
    //
    //                for(int k = 0; k < 4; k++) {
    //                    int x = i + dx[k], y = j + dy[k];
    //                    if(x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == '.' && !visit[x][y]) {
    //                        q.offer(new int[]{x, y});
    //                        visit[x][y] = true;
    //                    }
    //                }
    //            }
    //        }
    //
    //        return -1;
    //    }



    //433. 最小基因变化
    public int minMutation(String startGene, String endGene, String[] bank) {
        int step = -1;
        Set<String> hash = new HashSet<>();     // 记录该有效基因是否出现过
        hash.add(startGene);

        Queue<String> q = new LinkedList<>();   // 记录上次变化中的所有有效基因
        q.offer(startGene);

        Set<String> bankHash = new HashSet<>(); // 统计基因库中的所有基因
        for(String str : bank) bankHash.add(str);

        if(!bankHash.contains(endGene)) return -1;
        if(startGene.equals(endGene) && bankHash.contains(endGene)) return 0;

        while(!q.isEmpty()) {
            int sz = q.size();
            step++;

            while(sz-- > 0) {
                String s = q.poll();
                if(s.equals(endGene)) return step;

                // 让该基因与基因库中的基因对比，找出下标不同的字符进行替换
                for(int j = 0; j < bank.length; j++) {
                    char[] tmp = s.toCharArray();
                    for(int k = 0; k < 8; k++) {
                        if(tmp[k] != bank[j].charAt(k)) {
                            tmp[k] = bank[j].charAt(k);
                            break;
                        }
                    }
                    // 如果该替换后的字符串在基因库中，且之前没有出现过，则加入队列
                    String _tmp = new String(tmp);
                    if(!hash.contains(_tmp) && bankHash.contains(_tmp)) {
                        q.offer(_tmp);
                        hash.add(_tmp);
                    }
                }
            }
        }

        return -1;
    }


    //127. 单词接龙
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 将字典中的单词存储到哈希表
        Set<String> wordHash = new HashSet<>();
        wordHash.addAll(wordList);
        if(!wordHash.contains(endWord)) return 0;

        // 记录出现过的单词
        Set<String> hash = new HashSet<>();
        // 记录上一次转换的单词
        Queue<String> q = new LinkedList<>();
        hash.add(beginWord);
        q.offer(beginWord);

        int step = 0;
        while(!q.isEmpty()) {
            int sz = q.size();
            step++;

            while(sz-- > 0) {
                String word = q.poll();
                for(int i = 0; i < word.length(); i++) {
                    char[] tmp = word.toCharArray();
                    // 该单词的 i 下标字母变换 26次，每次进行判断是否
                    for(char ch = 'a'; ch <= 'z' ;ch++) {
                        tmp[i] = ch;
                        String _tmp = new String(tmp);
                        if(_tmp.equals(endWord)) return step + 1;
                        if(!hash.contains(_tmp) && wordHash.contains(_tmp)) {
                            q.offer(_tmp);
                            hash.add(_tmp);
                        }
                    }
                }

            }
        }

        return 0;
    }


    //  675. 为高尔夫比赛砍树
    //int ret, count, row, col;     // count 记录当前 start 到 end 的最短距离
    //    int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public int cutOffTree(List<List<Integer>> forest) {
    //        // 1. 确定砍树顺序，将所有树的位置按树的高度从小到大放到 优先级队列中
    //        row = forest.size(); col = forest.get(0).size();
    //        List<int[]> trees = new ArrayList<>();
    //        for(int i = 0; i < row; i++)
    //            for(int j = 0; j < col; j++)
    //                if(forest.get(i).get(j) > 1)
    //                    trees.add(new int[]{i, j});
    //        Collections.sort(trees, (o1, o2) -> {
    //            return forest.get(o1[0]).get(o1[1]) - forest.get(o2[0]).get(o2[1]);
    //        });
    //
    //        // 2. 每次从起始位置开始，每次走最短路径到下一个位置
    //        int[] start = {0,0};
    //        for(int[] tree : trees) {
    //            if(bfs(forest, start, tree) == -1) return -1;
    //            ret += count;
    //            start = tree;
    //        }
    //
    //        return ret;
    //    }
    //
    //    private int bfs(List<List<Integer>> forest, int[] start, int[] end) {
    //        if(start[0] == end[0] && start[1] == end[1]) return 0;
    //        boolean[][] visit = new boolean[row][col];      // 记录走过的位置
    //        Queue<int[]> q = new LinkedList<>();
    //        q.offer(start);
    //        visit[start[0]][start[1]] = true;
    //
    //        count = 0;
    //        while(!q.isEmpty()) {
    //            count++;
    //            int sz = q.size();
    //            for(int i = 0; i < sz; i++) {
    //                int[] path = q.poll();
    //                for(int k = 0; k < 4; k++) {
    //                    int x = path[0] + dx[k], y = path[1] + dy[k];
    //                    if(x >= 0 && x < row && y >= 0 && y < col && forest.get(x).get(y) > 0 && !visit[x][y]) {
    //                        if(x == end[0] && y == end[1]) return count;
    //                        q.offer(new int[]{x, y});
    //                        visit[x][y] = true;
    //                    }
    //                }
    //            }
    //        }
    //        return -1;
    //    }



    // LCR 107. 01 矩阵
    //int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public int[][] updateMatrix(int[][] mat) {
    //        int m = mat.length, n = mat[0].length;
    //        int[][] ret = new int[m][n];
    //        Queue<int[]> q = new LinkedList<>();
    //
    //        // 1. 将所有源点加入到 队列中，将非源点位置的值赋为 -1
    //        for(int i = 0; i < m; i++)
    //            for(int j = 0; j < n; j++)
    //                if(mat[i][j] == 0) {
    //                    ret[i][j] = 0;
    //                    q.offer(new int[]{i, j});
    //                } else {
    //                    ret[i][j] = -1;
    //                }
    //
    //        // 2. 将队列中的元素进行多源BFS遍历
    //        while(!q.isEmpty()) {
    //            int[] arr = q.poll();
    //            int a = arr[0], b = arr[1];
    //            for(int k = 0; k < 4; k++) {
    //                int x = a + dx[k], y = b + dy[k];
    //                if(x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1) {
    //                    ret[x][y] = ret[a][b] + 1;
    //                    q.offer(new int[]{x, y});
    //                }
    //            }
    //        }
    //
    //        return ret;
    //    }




    //1020. 飞地的数量
    int[] dx = new int[]{0,0,1,-1};
    int[] dy = new int[]{1,-1,0,0};

    public int numEnclaves(int[][] grid) {
        int sum = 0, row = grid.length, col = grid[0].length;
        boolean[][] visit = new boolean[row][col];

        for(int[] arr : grid)
            for(int x : arr)
                if(x == 1) sum++;

        // 将所有边界为陆地的坐标放入队列
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                if((i == 0 || i == row - 1 || j == 0 || j == col - 1) && grid[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    visit[i][j] = true;
                }

        // 进行多源BFS遍历，计算连通陆地的大小
        int count = 0;
        while(!q.isEmpty()) {
            count++;
            int[] t = q.poll();
            int i = t[0], j = t[1];
            for(int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == 1 && !visit[x][y]) {
                    visit[x][y] = true;
                    q.offer(new int[]{x, y});
                }
            }
        }

        return sum - count;
    }


    // 1765. 地图中的最高点
    // int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public int[][] highestPeak(int[][] isWater) {
    //        int row = isWater.length, col = isWater[0].length;
    //        int[][] ret = new int[row][col];
    //        Queue<int[]> q = new LinkedList<>();
    //
    //        for(int i = 0; i < row; i++) {
    //            for(int j = 0; j < col; j++) {
    //                if(isWater[i][j] == 1) {
    //                    ret[i][j] = 0;
    //                    q.offer(new int[]{i, j});
    //                } else {
    //                    ret[i][j] = -1;
    //                }
    //            }
    //        }
    //
    //        while(!q.isEmpty()) {
    //            int[] t = q.poll();
    //            int i = t[0], j = t[1];
    //            for(int k = 0; k < 4; k++) {
    //                int x = i + dx[k], y = j + dy[k];
    //                if(x >= 0 && x < row && y >= 0 && y < col && ret[x][y] == -1) {
    //                    ret[x][y] = ret[i][j] + 1;
    //                    q.offer(new int[]{x, y});
    //                }
    //            }
    //        }
    //        return ret;
    //    }



    //1162. 地图分析
    //int[] dx = new int[]{0,0,1,-1};
    //    int[] dy = new int[]{1,-1,0,0};
    //
    //    public int maxDistance(int[][] grid) {
    //        int row = grid.length, col = grid[0].length;
    //        Queue<int[]> q = new LinkedList<>();
    //
    //        for(int i = 0; i < row; i++)
    //            for(int j = 0; j < col; j++)
    //                if(grid[i][j] == 1)
    //                    q.offer(new int[]{i, j});
    //
    //        int ret = 0;
    //        while(!q.isEmpty()) {
    //            int[] t = q.poll();
    //            int i = t[0], j = t[1];
    //            for(int k = 0; k < 4; k++) {
    //                int x = i + dx[k], y = j + dy[k];
    //                if(x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == 0) {
    //                    grid[x][y] = grid[i][j] + 1;
    //                    ret = Math.max(ret, grid[x][y]);
    //                    q.offer(new int[]{x, y});
    //                }
    //            }
    //        }
    //
    //        return ret - 1;
    //    }



    // LCR 114. 火星词典
    boolean flag;       // 标记 str1长度 > str2的情况
    Map<Character, Integer> in;
    Map<Character, Set<Character>> edges;
    public String alienOrder(String[] words) {
        in = new HashMap<>(); //计算入度
        edges = new HashMap<>();  // 统计出度信息

        // 为所有字母添加入度为0， 防止入队失败
        for(String word : words)
            for(char ch : word.toCharArray())
                in.put(ch, 0);

        // 1. 构建图 并 统计各个课程的入度
        for(int i = 0; i < words.length - 1; i++) {
            for(int j = i + 1; j < words.length; j++) {
                add(words[i], words[j]);
                if(flag) return "";
            }

        }

        // 2. 将入度为0的结点加入队列
        Queue<Character> q = new LinkedList<>();
        for(Map.Entry<Character, Integer> e : in.entrySet()) {
            if(e.getValue() == 0) q.offer(e.getKey());
        }

        // 3. 尝试进行拓扑排序
        StringBuilder ret = new StringBuilder();
        while(!q.isEmpty()) {
            char ch = q.poll();
            ret.append(ch);

            if(!edges.containsKey(ch)) continue;
            for(Character c : edges.get(ch)) {
                in.put(c, in.get(c) - 1);
                if(in.get(c) == 0) q.offer(c);
            }
        }

        // 4. 判断
        for(Map.Entry<Character,Integer> e : in.entrySet()) {
            if(e.getValue() > 0) return "";
        }
        return ret.toString();
    }

    private void add(String str1, String str2) {
        int j = 0;
        for(; j < str1.length() && j < str2.length(); j++) {
            char ch1 = str1.charAt(j), ch2 = str2.charAt(j);
            if(ch1 != ch2) {    // 前面字母 < 后面字母
                if(!edges.containsKey(ch1)) edges.put(ch1, new HashSet<>());
                // 可能出现多次 ch1 -> ch2，不能重复增加入度次数
                if(!edges.get(ch1).contains(ch2)) {
                    edges.get(ch1).add(ch2);
                    in.put(ch2, in.get(ch2) + 1);
                }
                break;
            }
        }
        if(j == str2.length() && j < str1.length()) flag = true;
    }




    //207. 课程表
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. 构建图 并 统计各个课程的入度
        int[] t = new int[numCourses];      // 入度
        Map<Integer, List<Integer>> hash = new HashMap<>();     // 出度
        for(int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][0], b = prerequisites[i][1];
            if(!hash.containsKey(b)) {
                hash.put(b, new ArrayList<>());
            }
            hash.get(b).add(a);
            t[a]++;
        }

        // 2. 将所有入度为0的课程加入到队列中
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < t.length; i++) {
            if(t[i] == 0) q.offer(i);
        }

        // 3. 尝试拓扑排序
        while(!q.isEmpty()) {
            int course = q.poll();
            for(int x : hash.getOrDefault(course, new ArrayList<>())) { // 防止最后一个结点没有出度的情况
                t[x]--;
                if(t[x] == 0) q.offer(x);
            }
        }

        for(int x : t)
            if(x > 0) return false;
        return true;
    }




    //LCR 113. 课程表 II
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];     // 统计入度
        List<List<Integer>> edges = new ArrayList<>();    // 统计出度
        // 1. 构建图 并 统计各个课程的入度
        for(int i = 0; i < numCourses; i++) edges.add(new ArrayList<>());
        for(int i = 0; i < prerequisites.length; i++) {
            int a = prerequisites[i][0], b = prerequisites[i][1];
            edges.get(b).add(a);
            in[a]++;
        }

        // 2. 将所有入度为0的结点加入队列
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < numCourses; i++) {
            if(in[i] == 0) q.offer(i);
        }

        // 3. 尝试拓扑排序
        int index = 0;
        int[] ret = new int[numCourses];
        while(!q.isEmpty()) {
            int a = q.poll();
            ret[index++] = a;
            for(int x : edges.get(a)) {
                in[x]--;
                if(in[x] == 0) q.offer(x);
            }
        }

        for(int x : in) {
            if(x > 0) return new int[0];
        }
        return ret;
    }
}

